home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1998 / MacHack 1998.toast / Programming Contest / ~Solutions Submitted / Problem 10 - McMullen / Solution.cp < prev    next >
Encoding:
Text File  |  1998-06-19  |  7.2 KB  |  251 lines  |  [TEXT/CWIE]
  1. /*
  2. Problem 10 - Interpreter
  3.  
  4. Write an interpreter for this simple 32-bit integer language with 26 registers
  5. labeled A-Z.
  6.  
  7. type RegisterArray = array[0..25] of SInt32;
  8.  
  9. procedure Interpret( source: Handle; var result: RegisterArray );
  10.  
  11. source consists of a number of lines of the form:
  12.  
  13. [<label>:][<tab><instruction><tab><operand-list>]<cr>
  14.  
  15. <label> is a sequence of at least two alphanumerics (0-9a-zA-Z_)
  16. (casesensitive).
  17. <operand-list> is a sequence of operators seperated by commas
  18. other than the tabs and crs, no white space is allowed.
  19.  
  20. <instruction> (and appropriate operands are:
  21.  
  22. MOVE    <value>,<register>            (set <register> to <value>)
  23. ADD     <value1>,<value2>,<register>  (set <register> to <value1>+<value2>)
  24. SUB     <value1>,<value2>,<register>  (set <register> to <value1>-<value2>)
  25. JMP     <label>                       (jump to line labeled with <label>)
  26. JEQ     <value1>,<value2>,<label>     (jump to <label> if <value1> = <value2>)
  27. JLE     <value1>,<value2>,<label>     (jump to <label> if <value1> <= <value2>)
  28. JSR     <label>                       (jump to subroutine at <label>)
  29. RTS                                   (return from subroutine)
  30. PUSH    <value>                       (push value on to stack)
  31. POP     <register>                    (pop value from stack)
  32.  
  33. <register> is a single uppercase letter in the range A..Z
  34. <number> is an optional minus sign followed by decimal digits
  35. <value> is a <register> or a <number>
  36.  
  37. Note that the data stack and subroutine stack are independent stacks.  A RTS is
  38. used to stop the program (that is, consider that you have JSRed to the initial
  39. line of the source handle).  For example:
  40.  
  41.     PUSH    10
  42.     JSR    setA
  43.     JSE setB
  44.     RTS
  45. setA:
  46.     POP    A
  47.     RTS
  48. setB:    MOVE    A,B
  49.     RTS
  50.     
  51. Interpret takes the source handle and JSRs to it, presetting the registers
  52. according to the register array.  When the code returns, the register array is
  53. set to the final value of all the registers.  Both subroutine and data stacks
  54. should be large (at least 1000 entries each).
  55. */
  56.  
  57. #include "Solution.h"
  58.  
  59. // Fill in your solution and then submit this folder
  60.  
  61. // Team Name: #5
  62.  
  63. #include <string.h>
  64. #include <stdio.h>
  65.  
  66. const char* CharInLine(const char* src, char c)
  67. {
  68.     for (; *src != 0x0D; src++)
  69.         if (*src == c)
  70.             return src;
  71.     return nil;
  72. }
  73.  
  74. const char* FindOperand(const char*& src, char delimiter)
  75. {
  76.     const char* end;
  77.     for (end = src;*end != delimiter; end++);
  78.     char* result = new char[end - src + 1];
  79.     memcpy(result, src, end - src);
  80.     result[end - src] = 0;
  81.     src = end + 1;
  82.     return result;
  83. }
  84.  
  85. SInt32 GetOperandValue(const char* op, RegisterArray result)
  86. {
  87.     if (*op >= 'A' && *op <= 'Z')
  88.         return result[*op - 'A'];
  89.     SInt32 val;
  90.     sscanf(op, "%ld", &val);
  91.     return val;
  92. }
  93.  
  94. const char* FindLabel(const char* src,  const char* srcEnd, const char* label)
  95. {
  96.     const char* line = src;
  97.     while (line < srcEnd)
  98.     {
  99.         const char* eol;
  100.         for (eol = line; *eol!= 0x0D; eol++);
  101.         if (!eol)
  102.             eol = srcEnd;
  103.         if (strncmp(line, label, strlen(label)) == 0)
  104.             return line;
  105.         line = eol + 1;
  106.     }
  107.     return nil;
  108. }
  109.  
  110. pascal void Interpret( Handle source,  RegisterArray result )
  111. {
  112.     HLockHi(source);
  113.     UInt32 length = GetHandleSize(source);
  114.     const char* src = *source;
  115.     const char* eof = src + length;
  116.     const char* line = src;
  117.  
  118.     const char* operand1 = nil;
  119.     const char* operand2 = nil;
  120.     const char* operand3 = nil;
  121.     
  122.     const char* procStackStorage[1001];
  123.     const char** procStack = procStackStorage;
  124.  
  125.     SInt32 dataStackStorage[1001];
  126.     SInt32* dataStack = dataStackStorage;
  127.  
  128.     while (1)
  129.     {
  130.         delete [] operand1;
  131.         delete [] operand2;
  132.         delete [] operand3;
  133.         const char* eol;
  134.         for (eol = line; *eol!= 0x0D; eol++);
  135.         // skip label and tab, if any.
  136.         const char* currentInstruction = CharInLine(line,  0x09) + 1;
  137.         if (!currentInstruction)
  138.             return;
  139.  
  140.         if (strncmp(currentInstruction, "MOV", 3) == 0)
  141.         {
  142.             // MOVE    <value>,<register>            (set <register> to <value>)
  143.             line = CharInLine(currentInstruction,  0x09) + 1;
  144.             if (!line)
  145.                 return;
  146.             operand1 = FindOperand(line, ',');
  147.             operand2 = FindOperand(line, 0xD);
  148.             result[*operand2 - 'A'] = GetOperandValue(operand1, result);
  149.         }
  150.         else if (strncmp(currentInstruction, "ADD", 3) == 0)
  151.         {
  152.             //ADD     <value1>,<value2>,<register>  (set <register> to <value1>+<value2>)
  153.             line = CharInLine(currentInstruction,  0x09) + 1;
  154.             if (!line)
  155.                 return;
  156.             operand1 = FindOperand(line, ',');
  157.             operand2 = FindOperand(line, ',');
  158.             operand3 = FindOperand(line, 0xD);
  159.             result[*operand3 - 'A'] = GetOperandValue(operand1, result) + GetOperandValue(operand2, result);
  160.         }
  161.         else if (strncmp(currentInstruction, "SUB", 3) == 0)
  162.         {
  163.             //SUB     <value1>,<value2>,<register>  (set <register> to <value1>-<value2>)
  164.             line = CharInLine(currentInstruction,  0x09) + 1;
  165.             if (!line)
  166.                 return;
  167.             operand1 = FindOperand(line, ',');
  168.             operand2 = FindOperand(line, ',');
  169.             operand3 = FindOperand(line, 0xD);
  170.             result[*operand3 - 'A'] = GetOperandValue(operand1, result) - GetOperandValue(operand2, result);
  171.         }
  172.         else if (strncmp(currentInstruction, "JMP", 3) == 0)
  173.         {
  174.             //JMP     <label>                       (jump to line labeled with <label>)
  175.             line = CharInLine(currentInstruction,  0x09) + 1;
  176.             if (!line)
  177.                 return;
  178.             operand1 = FindOperand(line, 0xD);
  179.             line = FindLabel(line, eof, operand1);
  180.             continue;
  181.         }
  182.         else if (strncmp(currentInstruction, "JEQ", 3) == 0)
  183.         {
  184.             //JEQ     <value1>,<value2>,<label>     (jump to <label> if <value1> = <value2>)
  185.             line = CharInLine(currentInstruction,  0x09) + 1;
  186.             if (!line)
  187.                 return;
  188.             operand1 = FindOperand(line, ',');
  189.             operand2 = FindOperand(line, ',');
  190.             operand3 = FindOperand(line, 0xD);
  191.             if (GetOperandValue(operand1, result) == GetOperandValue(operand2, result))
  192.             {
  193.                 line = FindLabel(line, eof, operand3);
  194.                 continue;
  195.             }
  196.         }
  197.         else if (strncmp(currentInstruction, "JLE", 3) == 0)
  198.         {
  199.             //JLE     <value1>,<value2>,<label>     (jump to <label> if <value1> <= <value2>)
  200.             operand1 = FindOperand(line, ',');
  201.             operand2 = FindOperand(line, ',');
  202.             operand3 = FindOperand(line, 0xD);
  203.             if (GetOperandValue(operand1, result) <= GetOperandValue(operand2, result))
  204.             {
  205.                 line = FindLabel(line, eof, operand3);
  206.                 continue;
  207.             }
  208.         }
  209.         else if (strncmp(currentInstruction, "JSR", 3) == 0)
  210.         {
  211.             //JSR     <label>                       (jump to subroutine at <label>)
  212.             line = CharInLine(currentInstruction,  0x09) + 1;
  213.             if (!line)
  214.                 return;
  215.             operand1 = FindOperand(line, 0xD);
  216.             *procStack++ =  eol + 1;
  217.             line = FindLabel(src, eof, operand1);
  218.             continue;
  219.         }
  220.         else if (strncmp(currentInstruction, "RTS", 3) == 0)
  221.         {
  222.             //RTS                                   (return from subroutine)
  223.             if (procStack > procStackStorage)
  224.             {
  225.                 line = *--procStack;
  226.                 continue;
  227.             }
  228.             return;
  229.         }
  230.         else if (strncmp(currentInstruction, "PUS", 3) == 0)
  231.         {
  232.             //PUSH    <value>                       (push value on to stack)
  233.             line = CharInLine(currentInstruction,  0x09) + 1;
  234.             if (!line)
  235.                 return;
  236.             operand1 = FindOperand(line, 0xD);
  237.             *dataStack++ = GetOperandValue(operand1, result);    
  238.         }
  239.         else if (strncmp(currentInstruction, "POP", 3) == 0)
  240.         {
  241.             //POP     <register>                    (pop value from stack)
  242.             line = CharInLine(currentInstruction,  0x09) + 1;
  243.             if (!line)
  244.                 return;
  245.             operand1 = FindOperand(line, 0xD);
  246.             result[*operand1 - 'A'] = *--dataStack;    
  247.         }
  248.         line = eol + 1;
  249.     }
  250. }
  251.